package cn.genmer.test.security.leetcode.medium;

/**
 * @program: Algorithm_to_practice
 * @description: 122. 买卖股票的最佳时机 II
 * @author: Genmer
 * @create: 2020-10-15 13:10
 **/
public class StockSale2 {

    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        int profit = maxProfit(prices);
        System.out.println("利润是："+ profit);

    }

    /**
     *
     * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
     *
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 贪婪选择算法
     *
     * 分析
     * 观察题目,要求的是最大利润和.而且不存在多次买进的情况, 每次要买进必须将之前的卖出。
     * 要计算最大利润和, 我们每次对每一天选择的时候要么买，要么不买。那什么时候买，什么事不卖？
     * 其实和背包问题一样，只是这题更为简单，已经限制好了你挑选物品的顺序。
     *
     * 我们通过画图可以分析得出，每次再波谷底买进，每次再波峰卖出，则当前的利润和最大。遍历整个集合即可。
     *
     * 我的具体算法思路:
     * 用一个变量记录此时的方向，是向上递增，还是递减。如下面的d，初始状态设置为递减。
     * 每次检查当前数值和前面数值的差值，如果大于等于0，证明还在递增
     * 如果差值 小于0 证明已经递减, 波谷即为prices[i-1].
     * 累加利润
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices){
        // 判断股票是否上升
        int isRise = -1;
        int max=prices[0];
        int min= max;
        int totalProfit =0;

        for (int i=1; i<prices.length;i++){
            //根据波峰，后一天减去前一天的价钱如果大于0，说明股票在上升，可以继续持有
            if (prices[i]-prices[i-1]>=0){
                //进到这里说明 明天prices【i】还是上升的

                //上升标识位置
                isRise = 1;
                continue;
            } else {
                // 进到这说明 明天prices【i】要下跌了，就要卖掉了

                //置上升判断位为-1
                isRise = -1;
                //既然要卖掉了，当前最大的肯定是当前持有的股票 暂时的最高价
                max = prices[i-1];

                totalProfit += (max-min);
                min=prices[i];

            }
        }

        if (isRise == 1){
            //如果最后上升置于1，说明最后一天还有股票未卖出并且还是上升股票，这时候就必须卖出了
            max=prices[prices.length-1];
            totalProfit+=  (max-min);;
        }
        return totalProfit;
    }
}
